package 力扣;

/**
 给定的有序链表： [-10, -3, 0, 5, 9],

 一个可能的答案是：[0, -3, 9, -10, null, 5], 它可以表示下面这个高度平衡二叉搜索树：

      0
     / \
   -3   9
   /   /
 -10  5
 */

public class _109有序链表转换二叉搜索树 {
    public class ListNode {
        int val;
      ListNode next;
      ListNode() {}
      ListNode(int val) { this.val = val; }
      ListNode(int val, ListNode next) { this.val = val; this.next = next; }
  }
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {}
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
    public TreeNode sortedListToBST(ListNode head) {
        if( head == null ) return null;
        else if ( head.next == null ) return new TreeNode(head.val);

        ListNode pre = head;
        ListNode p = pre.next;  //中间节点
        ListNode q = p.next;
        while ( q!=null && q.next != null ){
            p = p.next;
            q = q.next.next;
            pre = pre.next;
        }
        //将中点左边的链表分开
        pre.next = null;
        TreeNode node = new TreeNode(p.val);
        node.left = sortedListToBST(head);
        node.right = sortedListToBST(p.next);
        return node;
    }

    public TreeNode sortedListToBST2(ListNode head) {
        return buildTree(head, null);
    }

    public TreeNode buildTree(ListNode left, ListNode right) {
        if (left == right) {
            return null;
        }
        ListNode mid = getMedian(left, right);
        TreeNode root = new TreeNode(mid.val);
        root.left = buildTree(left, mid);
        root.right = buildTree(mid.next, right);
        return root;
    }

    public ListNode getMedian(ListNode left, ListNode right) {
        ListNode fast = left;
        ListNode slow = left;
        while (fast != right && fast.next != right) {
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }



}
